/*
The MIT License (MIT)

Copyright (c) 2013 Mike Dapiran, Brian May, Richard Pospesel, and Bert Wierenga

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#pragma once

#include "hhdFunctions.h"

#include <string.h>
#include <cstdlib>

#include "hhdIList.hpp"
#include "hhdAssert.h"

namespace hhd
{
    /**
    * Vector<T> is a generic collection which implements the List<T> interface.  It is implemented
    * as a grow-able array.  Each time the Vector reaches capacity, the contents are copied into a
    * new array with a larger capacity which grows linearly.  Vectors only grow and never shrink.
    *
    * This data structure is not suited for very large collections of objects because after awhile,
    * the OS will be unable to allocate enough contiguous memory.  For large collections, use the
    * ArrayList<T>.
    *
    * @see ArrayList
    * @see List
    */
    template <typename T>
	class Vector : public IList<T>
    {
    public:
        /*
        * Default constructor for Vector<T>.  It has an initial capacity of 128 and it grows 128 places
        * each time it reaches capacity.
        */
        Vector()
        {
            _length = 0;
            _capacity = 16;
            _data = new T[_capacity];
        };

        /*
        * This constructor allows the user to define a custom initial capacity.  Grow length is 128.
        * @param in_initial_capacity The number of T you will be able to add to the Vector before it grows
        */
        Vector(size_t in_initial_capacity)
        {
            _length = 0;
            _capacity = in_initial_capacity;
			_data = new T[_capacity ? _capacity : 16];
        }


        /**
        * Boring old copy constructor; copies all the T by value.
        * @param in_other The Vector to copy.
        */
        Vector(const Vector& in_other)
        {
            _length = in_other._length;
            _capacity = in_other._capacity;
            _data = new T[_capacity];

            for(size_t k = 0; k < _length; k++)
            {
                _data[k] = in_other._data[k];
            }
        }

        ~Vector()
        {
			//baw	verification that all vectors are constructed properly
			HHD_ASSERT( _data != NULL );
			delete[] _data;
        };


        Vector& operator=(const Vector& other)
        {
            if(_data)
            {
                delete[] _data;
            }

            _length = other._length;
            _capacity = other._capacity;

            _data = new T[_capacity];
            for( size_t i = 0; i < _length; i++)
            {
                _data[i] = other._data[i];
            }

            return *this;
        };

        /**
        * Adds another value to the end of the Vector.  When the _data array reaches capacity, a new array of length
        * _length * 2 is created and the contents of _data are copied to this new array.  Finally,
        * _data is deleted and the new array is set to _data.
        * @param in_t The new value to add to the Vector.
        */
        void add(T in_t)
        {
            if(_length == _capacity)
            {
                grow();
            }

            _data[_length++] = in_t;
        };

        /**
        * The insert method places the passed in T to the passed in index, and moves all of the following
        * Ts up one index.
        * @param in_index The position in the array to place the new value.
        * @param in_t The value to place at location in_index.
        */
        void insert(size_t in_index, T in_t)
        {
            // if the index is greater than the number of elements, just tack it on the end
            if(in_index >= _length)
            {
                add(in_t);
                return;
            }

            // if no more space, increment size of the array
            if(_length == _capacity)
            {
                grow();
            }

            // shift up everything in front of the index one
            for(size_t i = _length; i > in_index; i--)
            {
                _data[i] = _data[i-1];
            }

            _data[in_index] = in_t;
            _length++;
        };

        /**
        * Sets the length of the Vector to 0.  The values stored in the array are not touched,
        * only the _length value is modified.
        */
        void clear()
        {
            _length = 0;
        };

        /**
        * Returns a copy of the value found at the passed index.  If the passed index is outside the
        * bounds of the array, an Exception is thrown.
        * @param in_index The index of the T to return.
        * @return Copy of the T found at in_index.
        */
        const T& get(size_t in_index) const
        {
            HHD_ASSERT(in_index < _length && in_index >= 0);
            return _data[in_index];
        };

        /**
        * Returns a reference to the T found at the passed index.  If the index is outside the
        * bounds of the array an Exception is thrown.
        * @param in_index The index of the T to return.
        * @return Reference to the T found at in_index.
        */
        T& get(size_t in_index)
        {
            HHD_ASSERT(in_index < _length && in_index >= 0);
            return _data[in_index];
        };

        /**
        * Removes and returns the T found at the passed index.  If the index is outside the
        * bounds of the underlying array, an Exception is thrown.
        * @param in_index The index of the T to remove and return.
        * @return The T found at in_index.
        */
        T removeAt(size_t in_index)
        {
            HHD_ASSERT(in_index < _length && in_index >= 0);

			T result = _data[in_index];
			_length--;
			for(size_t i = in_index; i < _length; i++)
			{
				_data[i] = _data[i+1];
			}
			return result;
        };

        /*
        * Removes the first instance of the specified value if it is in the vector.
        *
        * @param in_value The instance to remove.
        * @param preserve_order If
        *
        * @return Returns true if the value was removed
        */
        bool remove( T in_value, bool preserve_order = false )
        {
            if( preserve_order )
            {
                for(size_t i = 0; i < _length; i++ )
                {
                    if( _data[i] == in_value )
                    {
                        //found the first instance so shift the rest down
                        for( size_t j = i; j < _length-1; j++ )
                        {
                            _data[j] = _data[j+1];
                        }

                        _length--;
                        return true;
                    }
                }
                return false;
            }
            else
            {
                for(size_t i = 0; i < _length; i++ )
                {
                    if( _data[i] == in_value )
                    {
                        //just take the last item and set it at the index
                        _data[i] = _data[_length-1];
                        _length--;
                        return true;
                    }
                }
                return false;
            }
        }

        /**
        * Writes the passed in T to the passed in index over the pre-existing value.  Throws an
        * Exception when in_index is outside the bounds of the array.
        * @param in_index The index to write to.
        * @param in_t The value to write to in_index.
        */
        void set(size_t in_index, T in_t)
        {
            HHD_ASSERT(in_index < _length && in_index >= 0)
            _data[in_index] = in_t;
        };

        /**
        * Gets the number of elements which exist in the underlying array.
        * @return The number of elements in this Vector.
        */
        size_t size() const
        {
            return _length;
        };

        /**
        * Returns the size of the underlying array.
        * @return The capacity of this Vector before it has to grow.
        */
        size_t capacity() const
        {
            return _capacity;
        }

        /**
        * cast to a const array
        */
        operator const T* () const
        {
            return _data;
        }

        /**
        * Sort the the vector using an insertion sort
        **/
        void sort(int (*in_sort_function) (T, T))
        {
            size_t i, j, numLength = size();
            T key;
            for(j = 1; j < numLength; j++)    // Start with 1 (not 0)
            {
                key = get(j);
                for(i = j - 1; in_sort_function(get(i), key) < 0; i--)   // Larger values move up
                {
                    get(i+1) = get(i);
                }
                get(i+1) = key;    //Put key into its proper location
            }
            return;
        }

        /**
        * whether the vector contains the item already
        **/
        bool contains(const T& in_item) const
        {
            for(size_t k = 0; k < _length; k++)
			{
                if(_data[k] == in_item)
                {
                    return true;
                }
			}
            return false;
        }
    private:

        void grow()
        {
            _capacity *= 2;
            T* new_data = new T[_capacity];
            for(size_t k = 0; k < _length; k++)
            {
                new_data[k] = _data[k];
            }
            delete[] _data;
            _data = new_data;
        }

        size_t _length;
        size_t _capacity;

        T* _data;
    };
}
